home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / programm.ing / falcon / nt_dsp1.lzh / NT_DSP1.MSA / FFT / FFTR2BF.ASM < prev    next >
Encoding:
Assembly Source File  |  1990-01-17  |  13.6 KB  |  391 lines
  1. FFTR2BF    macro    points,passes,data,twiddle,temp
  2. ;
  3. ; Radix 2 Decimation-in-Time In-Place Block Floating Point
  4. ; Fast Fourier Transform Macro
  5. ;
  6. ;    Version with 2 butterflies, scratch storage
  7. ;
  8. ;    Complex input and output data
  9. ;        Real data in X memory
  10. ;        Imaginary data in Y memory
  11. ;    Normally ordered input data
  12. ;    Bit reversed output data
  13. ;    Twiddle factors lookup table
  14. ;        Cosine value in X memory
  15. ;        -Sine value in Y memory
  16. ;
  17. ; Macro Call - FFTR2BF points,passes,data,twiddle
  18. ;
  19. ;       points     number of points (4-32768, power of 2)
  20. ;       passes     number of fft passes (log2 points)
  21. ;       data       start of data buffer
  22. ;       twiddle    start of sine/cosine table
  23. ;       temp       low address of four consecutive x:y scratch memory
  24. ;                  (should be internal memory for fast program operation)
  25. ;                  on output, x:(temp)+2 contains the number of bits scaled;
  26. ;                  x:(temp)+3 shows, in base-4, the number of bits scaled per
  27. ;                  each stage
  28. ;
  29. ; Alters Data ALU Registers
  30. ;       x1      x0      y1      y0
  31. ;       a2      a1      a0      a
  32. ;       b2      b1      b0      b
  33. ;
  34. ; Alters Address Registers
  35. ;       r0      n0      m0
  36. ;       r1      n1      m1
  37. ;       r2      n2      m2
  38. ;       r3      n3      m3
  39. ;
  40. ;       r4      n4      m4
  41. ;       r5      n5      m5
  42. ;       r6      n6      m6
  43. ;       r7      n7      m7
  44. ;
  45. ; Alters Program Control Registers
  46. ;       pc      sr
  47. ;
  48. ; Uses 11 locations on System Stack
  49. ;
  50. ; Latest Revision - June 13, 1988
  51. ;
  52.         move    #temp+2,r2      ;initialize temporary data storage pointer
  53.         clr     a               ;initialize the number of bits scaled to zero
  54.         move    a,x:(r2)+
  55.         move    a,x:(r2)
  56.         move    #1,n2           ;initialize groups per pass
  57.         nop
  58.         move    n2,y:(r2)       ;initialize stage overflow indicator
  59.         move    #temp,r2        ;initialize temporary data storage pointer
  60.         move    #points,n0      ;initialize butterflies per group
  61.         move    #-1,m0          ;initialize address modifier for linear addressing
  62.         move    #points/4,n6    ;initialize twiddle offset
  63.         move    m0,m1           ;initialize address modifiers for linear addressing
  64.         move    m0,m4
  65.         move    m0,m5
  66.         move    m0,m2
  67.         move    m0,m3
  68.         move    m0,m7
  69.         move    #0,m6           ;initialize twiddle factor address modifier
  70.                                 ;  for reverse carry (bit reversed) addressing
  71. ;
  72. ; Perform all FFT passes with triple nested DO loop
  73. ;
  74.         do      #passes,_end_pass
  75.         move    n0,a1                           ;divide butterflies per group by two
  76.         lsr     a       #data,r0                ;and initialize A input pointer
  77.         move    a1,n0                           ;update butterflies per group
  78.         move    r0,r4                           ;initialize A output pointer
  79.         lua     (r0)+n0,r1                      ;initialize B input pointer
  80.         move    n0,n1
  81.         move    r1,r5                           ;initialize B output pointer
  82.         move    n0,n4                           ;initialize pointer offsets
  83.         move    n0,n5
  84.         move    x:(r0),x0                       ;clear downshift flag
  85.         movec   sr,x:(r0)
  86.         bclr    #10,x:(r0)
  87.         movec   x:(r0),sr
  88.         move    x0,x:(r0)
  89.  
  90.  
  91.         move    n2,r6                           ;get group count
  92.         move    m0,m6                           ;set linear addressing
  93.         move    y:(r0),b                        ;do t.f.=1 butterflies
  94.         move    y:(r1),a
  95.         sub     a,b             ab,l:(r2)+
  96.  
  97.         do      n0,_end_bf0
  98.         addl    b,a     x:(r0)+,b       b,y:(r5)
  99.         move            x:(r1)+,a       a,y:(r4)
  100.         sub     a,b             ab,l:(r2)-
  101.         addl    b,a     b,x:(r5)+       y:(r0),b
  102.         move            a,x:(r4)+       y:(r1),a
  103.         jls     _ov_bf0_go                      ;test for overflow--FORCE SHORT JUMP WHEN POSSIBLE
  104. _ov_bf0_ret
  105.         sub     a,b             ab,l:(r2)+
  106. _end_bf0
  107.         lua     (r2)-,r2
  108.  
  109.         lua     (r6)-,r6                        ;update pointers and test for no more groups
  110.         lua     (r4)+n4,r4
  111.         move    #0,m6                           ;set bit-reverse mode for t.f.
  112.         move    r6,a
  113.         move    r6,n7                           ;save group counter
  114.         move    #twiddle,r6
  115.         lua     (r0)+n0,r0
  116.         lua     (r1)+n1,r1
  117.         lua     (r6)+n6,r6
  118.         tst     a       (r5)+n5
  119.         jle     _sk_grp
  120.  
  121.  
  122.         do      n7,_end_grp                     ;do the normal butterflies
  123.         move    r2,r7                           ;set pointer to temp storage
  124.         move    x:(r1),x1       y:(r6),y0       ;lookup -sine value
  125.         move    x:(r6)+n6,x0    y:(r0),b        ;lookup cosine value
  126.  
  127.         mac     x1,y0,b         b,x:(r7)+       y:(r1)+,y1      ;Radix 2 DIT butterfly kernel
  128.         do      n0,_end_bf2
  129.         macr    x0,y1,b         x1,x:(r7)-      y:(r0),a
  130.         subl    b,a             x:(r0),b        b,y:(r4)
  131.         mac     x1,x0,b         x:(r1),x1       b,y:(r7)
  132.         macr    -y1,y0,b        x:(r0)+,a       a,y:(r5)
  133.         subl    b,a             b,x:(r4)+
  134.         move                    a,x:(r5)+       y:(r0),b
  135.         jls     _ov_bf2_go                      ;test for overflow --FORCE SHORT JUMP WHEN POSSIBLE
  136. _ov_bf2_ret
  137.         mac     x1,y0,b         b,x:(r7)+       y:(r1)+,y1
  138. _end_bf2
  139.  
  140.         lua     (r1)-,r1
  141.         lua     (r5)+n5,r5                      ;update data pointers
  142.         lua     (r1)+n1,r1
  143.         lua     (r0)+n0,r0
  144.         lua     (r4)+n4,r4
  145. _end_grp
  146. _sk_grp
  147.         move    n2,a1
  148.         lsl     a                               ;multiply groups per pass by two
  149.         move    a1,n2                           ;update groups per pass
  150.  
  151.         move    #temp+3,r2
  152.         nop
  153.         move    y:(r2),a1
  154.         lsl     a
  155.         lsl     a
  156.         move    a1,y:(r2)
  157.         move    #temp,r2
  158. _end_pass
  159.  
  160.         move    x:(r0),x0                       ;clear downshift flag
  161.         movec   sr,x:(r0)
  162.         bclr    #10,x:(r0)
  163.         movec   x:(r0),sr
  164.         move    x0,x:(r0)
  165.         jmp     _bsfft_end
  166.  
  167. ;
  168. ;  OVERFLOW MANAGEMENT CODE
  169. ;
  170.  
  171. ;
  172. ; overflow correction code, full butterfly
  173. ;
  174. _ov_bf2_go
  175.         lua     (r4)-,r7
  176.         lua     (r5)-,r3
  177.         movec   sr,y:(r7)                       ;reset limit flag
  178.         bclr    #6,y:(r7)
  179.         movec   y:(r7),sr
  180.  
  181.  
  182.         jclr    #10,y:(r7),_bf2_ndov            ;double overflow, previous overflow
  183.  
  184.         jsr     _c_ov                           ;increment the scaling counter
  185.         jsr     _d_sc                           ;scale all the data
  186.  
  187.         lua     (r5)-,r3
  188.         move                    y1,a            ;scale down data element
  189.         move    x:(r2)+,b       a,y1            ;recompute butterfly
  190.         move            x:(r2)-,a
  191.         move            a,x1
  192.         mac     x1,y0,b
  193.         macr    x0,y1,b         x:(r2),a
  194.         subl    b,a             b,y:(r7)
  195.         move                    y:(r2),b
  196.         mac     x1,x0,b         a,y:(r3)
  197.         macr    -y1,y0,b        y:(r2),a
  198.         subl    b,a     b,x:(r7)
  199.         move            a,x:(r3)
  200.  
  201.         move            x:(r1),x1               ;reload data for next butterfly
  202.         move            y:(r0),b
  203.  
  204.         move    r2,r7                           ;recover temp storage pointer
  205.         jmp     _ov_bf2_ret
  206.  
  207.  
  208. _bf2_ndov
  209.         bset    #10,y:(r7)                      ;set downshift
  210.         movec   y:(r7),sr
  211.         jsr     _c_ov                           ;increment the scaling counter
  212.  
  213.         move            x:(r2)+,b               ;recompute butterfly
  214.         move            x:(r2)-,x1
  215.         mac     x1,y0,b
  216.         macr    x0,y1,b         x:(r2),a
  217.         subl    b,a             b,y:(r7)
  218.         move                    y:(r2),b
  219.         mac     x1,x0,b         a,y:(r3)
  220.         macr    -y1,y0,b        y:(r2),a
  221.         subl    b,a     b,x:(r7)
  222.         move            a,x:(r3)
  223.  
  224.         jlc     _bf2_sk_1                       ;double overflow, NO previous overflow
  225.         movec   sr,y:(r7)                       ;reset limit bit
  226.         bclr    #6,y:(r7)
  227.         movec   y:(r7),sr
  228.         jsr     _c_ov                           ;increment the scaling counter
  229.  
  230.         jsr     _d_sc                           ;scale all the data down by one bit
  231.  
  232.         lua     (r5)-,r3
  233.         move            x:(r2)+,b               ;recompute butterfly
  234.         move            x:(r2)-,x1
  235.         mac     x1,y0,b
  236.         macr    x0,y1,b         x:(r2),a
  237.         asr     b
  238.         asr     a
  239.         subl    b,a             b,y:(r7)
  240.         move                    y:(r2),b
  241.         mac     x1,x0,b         a,y:(r3)
  242.         macr    -y1,y0,b        y:(r2),a
  243.         asr     b
  244.         asr     a
  245.         subl    b,a     b,x:(r7)
  246.         move            a,x:(r3)
  247.  
  248. _bf2_sk_1
  249.         jsr     _pb_sc                          ;scale previously completed butterflies
  250.  
  251.         move            x:(r1),x1               ;reload data for next butterfly
  252.         move            y:(r0),b
  253.         move    r2,r7                           ;recover temp storage pointer
  254.         jmp     _ov_bf2_ret                     ;return to the butterfly loop
  255.  
  256. ;
  257. ; butterfly 0 overflow correction code
  258. ;
  259. _ov_bf0_go
  260.         lua     (r4)-,r7                        ;recover data addresses
  261.         lua     (r5)-,r3
  262.         movec   sr,x:(r7)                       ;reset limit flag
  263.         bclr    #6,x:(r7)
  264.         bset    #10,x:(r7)                      ;set downshift
  265.         movec   x:(r7),sr
  266.         jsr     _c_ov                           ;increment the scaling counter
  267.  
  268.         move            l:(r2)+,ab              ;recompute butterfly
  269.         sub     a,b
  270.         addl    b,a             b,y:(r3)
  271.         move                    a,y:(r7)
  272.         move            l:(r2)-,ab
  273.         sub     a,b
  274.         addl    b,a     b,x:(r3)
  275.         move            a,x:(r7)
  276.  
  277.         move    #data,r3                        ;set index registers
  278.         move    n0,n3
  279.         move    n0,n7
  280.         lua     (r3)+n3,r7
  281.  
  282.         move    lc,a                            ;get butterfly loop count
  283.         move    n0,b                            ;compute number of butterflies to scale
  284.         sub     a,b
  285.         jle     _bf0_b_sk
  286.  
  287.         lsl     b                               ;precorrect for shift
  288.         do      b,_bf0_spb                      ;scale these butterflies
  289.         move    x:(r3),a        y:(r7),b
  290.         move    a,x:(r3)        b,y:(r7)
  291.         move    y:(r3),a        x:(r7),b
  292.         move    a,y:(r3)+       b,x:(r7)+
  293. _bf0_spb
  294.  
  295. _bf0_b_sk
  296.         move    y:(r0),b                        ;recover data for next butterfly
  297.         move    y:(r1),a
  298.  
  299.         jmp     _ov_bf0_ret                     ;return to the butterfly loop
  300.  
  301. ;
  302. ;  SUBROUTINES
  303. ;
  304. ;  _d_sc:  Subroutine to scale down the entire stage by a factor of
  305. ;          two in the event of a second overflow in a stage.
  306. ;
  307. _d_sc
  308.         move    #data,r3                        ;set pointer to start of data
  309.  
  310.         do      #points,_sc_lp
  311.         move    l:(r3),ab
  312.         move    ab,l:(r3)+
  313. _sc_lp
  314.  
  315.         rts
  316.  
  317. ;
  318. ; _pb_sc   Subroutine to scale previously completed butterflies
  319. ;
  320. _pb_sc
  321.         move    #2,r3                           ;set stack pointer to group loop counter
  322.         movec   sp,a
  323.         move    r3,b
  324.         movec   sp,r3                           ;save stack pointer
  325.         sub     b,a
  326.         lsl     a
  327.         movec   a,sp
  328.  
  329.         move    n2,a                            ;compute number of completed groups
  330.         movec   ssl,b
  331.         move    n2,a
  332.         sub     b,a
  333.         movec   r3,sp                           ;restore stack pointer
  334.         move    #data,r3                        ;set index registers
  335.         move    n0,n3
  336.         move    n0,n7
  337.         lua     (r3)+n3,r7
  338.  
  339.         jle     _pb_g_sk
  340.  
  341.         lsl     a                               ;precorrect loop count for shift
  342.         do      a,_pb_glp                       ;scale down these groups
  343.         do      n0,_pb_blp_1
  344.         move    x:(r3),a        y:(r7),b
  345.         move    a,x:(r3)        b,y:(r7)
  346.         move    y:(r3),a        x:(r7),b
  347.         move    a,y:(r3)+       b,x:(r7)+
  348. _pb_blp_1
  349.         lua     (r3)+n3,r3
  350.         lua     (r7)+n7,r7
  351. _pb_glp
  352.  
  353. _pb_g_sk
  354.         move    lc,a                            ;get butterfly loop count
  355.         move    n0,b                            ;compute number of butterflies to scale
  356.         sub     a,b
  357.         jle     _pb_b_sk
  358.  
  359.         lsl     b                               ;precorrect for shift
  360.         do      b,_pb_blp_2                     ;scale these butterflies
  361.         move    x:(r3),a        y:(r7),b
  362.         move    a,x:(r3)        b,y:(r7)
  363.         move    y:(r3),a        x:(r7),b
  364.         move    a,y:(r3)+       b,x:(r7)+
  365. _pb_blp_2
  366.  
  367. _pb_b_sk
  368.  
  369.         rts
  370. ;
  371. ;  _c_ov:  Subroutine to increment the number-of-bits-scaled counter
  372. ;
  373. _c_ov
  374.         move    #temp+2,r2              ;change pointer to (temp)+2
  375.         nop
  376.         move    r3,y:(r2)               ;save r3
  377.         move    x:(r2),r3               ;increment number-of-bits-scaled
  378.         nop
  379.         lua     (r3)+,r3
  380.         nop
  381.         move    r3,x:(r2)               ;store number-of-bits-scaled
  382.         move    y:(r2)+,r3              ;restore r3 and reset (temp) pointer
  383.         move    l:(r2),ab
  384.         add     b,a
  385.         lsl     a
  386.         move    a,x:(r2)
  387.         move    #temp,r2
  388.         rts
  389.  
  390. _bsfft_end
  391.         endm^Z